from typing import List
class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        d = ((-1, 0), (1, 0), (0, -1), (0, 1))
        m = len(grid)
        if not m:
            return 0
        n = len(grid[0])

        def get_all_rot(grid):
            data = []
            # print("inget_all", grid)
            for i in range(m):
                for j in range(n):
                    if grid[i][j]==2:
                        data.append([i,j])
            return data
                        
        def in_area(x ,y):
            return x >= 0 and y >= 0 and x < m and y < n

        def backtrack(grid, times):

            while 1: 
                rot = get_all_rot(grid)
                if not rot:
                    return 0
                sign = False
                for x, y in rot:
                    for i in d:
                        new_x = i[0] + x
                        new_y = i[1] + y

                        # 合法的位置
                        if  in_area(new_x, new_y) and grid[new_x][new_y] == 1:
                            grid[new_x][new_y] = 2
                            sign = True
                if sign == False:
                    return times
                times += 1
        s = backtrack(grid, 0)
        for i in range(m):
            if 1 in grid[i]:
                return -1
        return s
if __name__ == "__main__":
    # s = [[2,1,1],[1,1,0],[0,1,1]]
    # print(Solution().orangesRotting(s) )
    # b= [[2,1,1],[0,1,1],[1,0,1]]
    # print(Solution().orangesRotting(b) )
    print(Solution().orangesRotting([[0]]) )


